This invention relates to cryptosystems, and more particularly to a technique for strengthening a cryptosystem without substantially increasing the complexity thereof.
In modern communications, it is often desirable to communicate in secrecy, and it is common practice to encode, or encipher, a message prior to transmission and to then decode, or decipher, the received cryptogram in order to obtain the original message. In many cases, the security requirements are not substantial and, therefore, relatively simple cryptosystems will suffice. However, in some applications, a very high degree of communication security is required, and a cryptosystem must be employed which is substantially immune to cryptanalysis.
Standard techniques for achieving the desired high degree of communication security have emphasized the design of the encipherer and decipherer. Some employ highly complex encryption algorithms and are, from a practical viewpoint, immune to a cryptanalysis attack. However, such an encryption algorithm will require rather complex and costly encipherer/decipherer equipment. When anything but the highest level of security is required, the use of such complicated equipment may not be warranted.
An alternative technique is the use of a source coding scheme. It has been pointed out by C. E. Shannon, "Communication Theory of Secrecy Systems," Bell System Technical Journal, Vol. 28, pages 656-715, Oct. 1949, that the number of cryptogram letters (which he refers to as the "unicity distance"), needed to successfully cryptoanalyze a cryptogram is inversely proportional to the message redundancy. Thus, the security of a cryptosystem could be strengthened by using a good source coding scheme which actually reduces the redundancy of the messages. If the prime concern is to deceive the cryptanalyst the cryptosystem can be strengthened by modifying the appearance of the messages, and a few source coding schemes such as the Huffman codes and run-length codes discussed by R. G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, N.Y. 1968, have been studied in greater detail. Not only can these source coding schemes reduce the redundancy of the messages, but their main objective is the reduction of the band width requirements of the communication channel. These complicated source coding schemes, however, suffer from the same disadvantage as the very complicated enciphering and deciphering techniques in that they are rather complex and costly and, in many applications, are not warranted by the security requirements. If the channel bandwidth is available, the primary function of these source coding schemes, i.e., the reduction in the bandwidth requirements of the communication channel, is no longer needed and the use of these source coding schemes purely for the purpose of increasing communication security may constitute an "overkill".